{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Tasks You Can Assign"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #queue #array #binary-search #sorting #monotonic-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #队列 #数组 #二分查找 #排序 #单调队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxTaskAssign"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #你可以安排的最多任务数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你&nbsp;<code>n</code>&nbsp;个任务和&nbsp;<code>m</code>&nbsp;个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>tasks</code>&nbsp;中，第 <code>i</code>&nbsp;个任务需要&nbsp;<code>tasks[i]</code>&nbsp;的力量才能完成。每个工人的力量值保存在下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>workers</code>&nbsp;中，第&nbsp;<code>j</code>&nbsp;个工人的力量值为&nbsp;<code>workers[j]</code>&nbsp;。每个工人只能完成 <strong>一个</strong>&nbsp;任务，且力量值需要 <strong>大于等于</strong>&nbsp;该任务的力量要求值（即&nbsp;<code>workers[j] &gt;= tasks[i]</code>&nbsp;）。</p>\n",
    "\n",
    "<p>除此以外，你还有&nbsp;<code>pills</code>&nbsp;个神奇药丸，可以给 <strong>一个工人的力量值</strong>&nbsp;增加&nbsp;<code>strength</code>&nbsp;。你可以决定给哪些工人使用药丸，但每个工人&nbsp;<strong>最多</strong>&nbsp;只能使用&nbsp;<strong>一片</strong>&nbsp;药丸。</p>\n",
    "\n",
    "<p>给你下标从 <strong>0</strong>&nbsp;开始的整数数组<code>tasks</code> 和&nbsp;<code>workers</code>&nbsp;以及两个整数&nbsp;<code>pills</code> 和&nbsp;<code>strength</code>&nbsp;，请你返回 <strong>最多</strong>&nbsp;有多少个任务可以被完成。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [<em><strong>3</strong></em>,<em><strong>2</strong></em>,<em><strong>1</strong></em>], workers = [<em><strong>0</strong></em>,<em><strong>3</strong></em>,<em><strong>3</strong></em>], pills = 1, strength = 1\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "我们可以按照如下方案安排药丸：\n",
    "- 给 0 号工人药丸。\n",
    "- 0 号工人完成任务 2（0 + 1 &gt;= 1）\n",
    "- 1 号工人完成任务 1（3 &gt;= 2）\n",
    "- 2 号工人完成任务 0（3 &gt;= 3）\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [<em><strong>5</strong></em>,4], workers = [<em><strong>0</strong></em>,0,0], pills = 1, strength = 5\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>\n",
    "我们可以按照如下方案安排药丸：\n",
    "- 给 0 号工人药丸。\n",
    "- 0 号工人完成任务 0（0 + 5 &gt;= 5）\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [<em><strong>10</strong></em>,<em><strong>15</strong></em>,30], workers = [<em><strong>0</strong></em>,<em><strong>10</strong></em>,10,10,10], pills = 3, strength = 10\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "我们可以按照如下方案安排药丸：\n",
    "- 给 0 号和 1 号工人药丸。\n",
    "- 0 号工人完成任务 0（0 + 10 &gt;= 10）\n",
    "- 1 号工人完成任务 1（10 + 10 &gt;= 15）\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [<em><strong>5</strong></em>,9,<em><strong>8</strong></em>,<em><strong>5</strong></em>,9], workers = [1,<em><strong>6</strong></em>,<em><strong>4</strong></em>,2,<em><strong>6</strong></em>], pills = 1, strength = 5\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "我们可以按照如下方案安排药丸：\n",
    "- 给 2 号工人药丸。\n",
    "- 1 号工人完成任务 0（6 &gt;= 5）\n",
    "- 2 号工人完成任务 2（4 + 5 &gt;= 8）\n",
    "- 4 号工人完成任务 3（6 &gt;= 5）\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == tasks.length</code></li>\n",
    "\t<li><code>m == workers.length</code></li>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= pills &lt;= m</code></li>\n",
    "\t<li><code>0 &lt;= tasks[i], workers[j], strength &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-tasks-you-can-assign](https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-tasks-you-can-assign](https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,1]\\n[0,3,3]\\n1\\n1', '[5,4]\\n[0,0,0]\\n1\\n5', '[10,15,30]\\n[0,10,10,10,10]\\n3\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n,m = len(tasks),len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        left, right = 0, min(n,m)\n",
    "        def check(k):\n",
    "            able_tasks = deque()\n",
    "            j = 0\n",
    "            p = pills\n",
    "            for i in range(k):\n",
    "                cur_w = workers[-k+i]\n",
    "                while j<k  and tasks[j]<=cur_w+strength:\n",
    "                    able_tasks.append(tasks[j])\n",
    "                    j+=1\n",
    "                if not able_tasks:\n",
    "                    return False\n",
    "                if cur_w>=able_tasks[0]:\n",
    "                    able_tasks.popleft()\n",
    "                else:\n",
    "                    if p==0:\n",
    "                        return False\n",
    "                    able_tasks.pop()\n",
    "                    p-=1\n",
    "            return True\n",
    "                \n",
    "\n",
    "        while left<right:\n",
    "            mid = (left+right+1)//2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        s = 0\n",
    "        e = min(len(tasks), len(workers)) + 1\n",
    "        while s + 1 < e:\n",
    "            m = (s + e) // 2\n",
    "            #print(\"try\", m)\n",
    "            # Match workers[-m:] to tasks[:m]\n",
    "            i2 = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(len(workers) - m, len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < m and tasks[i2] <= w + strength:\n",
    "                    valid_tasks.append(tasks[i2])\n",
    "                    i2 += 1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    # No need for pill\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                e = m\n",
    "            else:\n",
    "                s = m\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        task_len, worker_len = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        max_task_num = 0\n",
    "        max_wt_num = min(task_len, worker_len) + 1\n",
    "        while max_task_num + 1 < max_wt_num:\n",
    "            mid = (max_task_num + max_wt_num) // 2\n",
    "            task_i = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(worker_len - mid, worker_len):\n",
    "                worker = workers[j]\n",
    "                while task_i < mid and tasks[task_i] <= worker + strength:\n",
    "                    valid_tasks.append(tasks[task_i])\n",
    "                    task_i += 1\n",
    "                if not valid_tasks: \n",
    "                    fail = True\n",
    "                    break\n",
    "                elif valid_tasks[0] <= worker:\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail: max_wt_num = mid\n",
    "            else: max_task_num = mid\n",
    "        return max_task_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        s = 0\n",
    "        e = min(len(tasks), len(workers)) + 1\n",
    "        \n",
    "        while s + 1 < e:\n",
    "            m = (s + e) // 2\n",
    "            #print(\"try\", m)\n",
    "            # Match workers[-m:] to tasks[:m]\n",
    "            i2 = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(len(workers) - m, len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < m and tasks[i2] <= w + strength:\n",
    "                    valid_tasks.append(tasks[i2])\n",
    "                    i2 += 1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    # No need for pill\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                e = m\n",
    "            else:\n",
    "                s = m\n",
    "\n",
    "        return s\n",
    "\n",
    "# 作者：灵剑2012\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        m, n = len(workers), len(tasks)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        def f(tl, tr, wl, wr, pills, strength):\n",
    "            if wl < 0:\n",
    "                return False\n",
    "            cnt = 0\n",
    "            q = deque()\n",
    "            j = tl\n",
    "            for i in range(wl, wr):\n",
    "                while j < tr:\n",
    "                    if workers[i] >= tasks[j]:\n",
    "                        q.append(j)\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        break      \n",
    "                if q and tasks[q[0]] <= workers[i]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    while j < tr:\n",
    "                        if workers[i] + strength >= tasks[j]:\n",
    "                            q.append(j)\n",
    "                            j += 1 \n",
    "                        else:\n",
    "                            break\n",
    "                    if q and workers[i] + strength >= tasks[q[-1]]:\n",
    "                        cnt += 1\n",
    "                        q.pop()\n",
    "                    else:\n",
    "                        return False\n",
    "            return cnt <= pills\n",
    "        left, right = -1, n + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if f(0, mid, m - mid, m, pills, strength):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        \n",
    "        # def check(workers, tasks):\n",
    "        #     c = 0#药丸数量\n",
    "        #     while tasks:#降序弹出\n",
    "        #         n = tasks.pop()\n",
    "        #         if workers[-1] + strength < n:#如果加上药丸都无法完成\n",
    "        #             return False\n",
    "        #         elif workers[-1] < n:#需要吃药丸\n",
    "        #             idx = bisect.bisect_left(workers, n - strength)\n",
    "        #             #二分找到可以吃药丸完成任务中最小的工人\n",
    "\n",
    "        #             workers.pop(idx)#弹出该工人\n",
    "        #             c += 1#药丸数量+1\n",
    "\n",
    "        #             if c > pills:#如果超出药丸总数则无法完成\n",
    "        #                 return False\n",
    "\n",
    "        #         else:#不需要吃药丸\n",
    "        #             workers.pop()#弹出最强的\n",
    "        #     return True\n",
    "\n",
    "        # tasks.sort()#排序\n",
    "        # workers.sort()\n",
    "        # l = 0#左边界\n",
    "        # r = min(len(tasks), len(workers))#右边界\n",
    "        # while l < r:\n",
    "        #     mid = (l + r + 1) // 2\n",
    "        #     if check(workers[-mid:], tasks[:mid]):#可以完成，更新左边界\n",
    "        #         l = mid\n",
    "        #     else:#无法完成，更新右边界\n",
    "        #         r = mid - 1\n",
    "        # return l\n",
    "#二分查找最多完成任务。 每次二分查找到的任务数量，按照降序取出对应数量工人，按照升序取出对应数量任务。 降序遍历任务，当任务比当前最强的工人加上药丸力量还大时，说明无法完成对应数量任务。 当任务比当前最强的工人力量大时，二分找到吃下药丸后能完成任务的最小工人完成任务，并将药丸数量+1。 否则将最强工人弹出，因为任务和工人都是有序的，如果存在更小的工人可以完成此任务那么一定能完成剩余任务，所以这里不需要再二分。 结束后如果药丸数量不大于pills时则说明可以完成，更新左边界，否则无法完成更新右边界。\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        s = 0\n",
    "        e = min(len(tasks), len(workers)) + 1\n",
    "        while s + 1 < e:\n",
    "            m = (s + e) // 2\n",
    "            #print(\"try\", m)\n",
    "            # Match workers[-m:] to tasks[:m]\n",
    "            i2 = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(len(workers) - m, len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < m and tasks[i2] <= w + strength:\n",
    "                    valid_tasks.append(tasks[i2])\n",
    "                    i2 += 1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    # No need for pill\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                e = m\n",
    "            else:\n",
    "                s = m\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        s = 0\n",
    "        e = min(len(tasks), len(workers)) + 1\n",
    "        while s + 1 < e:\n",
    "            m = (s + e) // 2\n",
    "            #print(\"try\", m)\n",
    "            # Match workers[-m:] to tasks[:m]\n",
    "            i2 = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(len(workers) - m, len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < m and tasks[i2] <= w + strength:\n",
    "                    valid_tasks.append(tasks[i2])\n",
    "                    i2 += 1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    # No need for pill\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                e = m\n",
    "            else:\n",
    "                s = m\n",
    "        return s\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        s = 0\n",
    "        e = min(len(tasks), len(workers)) + 1\n",
    "        while s + 1 < e:\n",
    "            m = (s + e) // 2\n",
    "            #print(\"try\", m)\n",
    "            # Match workers[-m:] to tasks[:m]\n",
    "            i2 = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(len(workers) - m, len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < m and tasks[i2] <= w + strength:\n",
    "                    valid_tasks.append(tasks[i2])\n",
    "                    i2 += 1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    # No need for pill\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                e = m\n",
    "            else:\n",
    "                s = m\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        s = 0\n",
    "        e = min(len(tasks), len(workers)) + 1\n",
    "        while s + 1 < e:\n",
    "            m = (s + e) // 2\n",
    "            #print(\"try\", m)\n",
    "            # Match workers[-m:] to tasks[:m]\n",
    "            i2 = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(len(workers) - m, len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < m and tasks[i2] <= w + strength:\n",
    "                    valid_tasks.append(tasks[i2])\n",
    "                    i2 += 1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    # No need for pill\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                e = m\n",
    "            else:\n",
    "                s = m\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        s = 0\n",
    "        e = min(len(tasks), len(workers)) + 1\n",
    "        while s + 1 < e:\n",
    "            m = (s + e) // 2\n",
    "            #print(\"try\", m)\n",
    "            # Match workers[-m:] to tasks[:m]\n",
    "            i2 = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(len(workers) - m, len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < m and tasks[i2] <= w + strength:\n",
    "                    valid_tasks.append(tasks[i2])\n",
    "                    i2 += 1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    # No need for pill\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                e = m\n",
    "            else:\n",
    "                s = m\n",
    "        return s\n",
    "\n",
    "# 作者：灵剑2012\n",
    "# 链接：https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/solutions/1100374/ji-yu-er-fen-dan-diao-dui-lie-de-onlogns-zy8q/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        result = 0\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        left, right = 0, min(len(tasks), len(workers))\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.check(tasks, workers, strength, pills, mid):\n",
    "                result = mid \n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid \n",
    "        if self.check(tasks, workers, strength, pills, left):\n",
    "            result = left \n",
    "        return result \n",
    "    \n",
    "    def check(self, tasks, workers, strength, pills, target):\n",
    "        candidates = deque()\n",
    "        pos = len(workers) - 1 \n",
    "        for i in range(target - 1, -1, -1):\n",
    "            while pos >= len(workers) - target and workers[pos] + strength >= tasks[i]:\n",
    "                candidates.appendleft(workers[pos])\n",
    "                pos -= 1 \n",
    "            if not candidates:\n",
    "                return False \n",
    "            elif candidates[-1] >= tasks[i]:\n",
    "                candidates.pop()\n",
    "            else:\n",
    "                if pills == 0:\n",
    "                    return False \n",
    "                candidates.popleft()\n",
    "                pills -= 1\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        s = 0\n",
    "        e = min(len(tasks), len(workers)) + 1\n",
    "        while s + 1 < e:\n",
    "            m = (s + e) // 2\n",
    "            #print(\"try\", m)\n",
    "            # Match workers[-m:] to tasks[:m]\n",
    "            i2 = 0\n",
    "            p = pills\n",
    "            fail = False\n",
    "            valid_tasks = deque()\n",
    "            for j in range(len(workers) - m, len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < m and tasks[i2] <= w + strength:\n",
    "                    valid_tasks.append(tasks[i2])\n",
    "                    i2 += 1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    # No need for pill\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p -= 1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                e = m\n",
    "            else:\n",
    "                s = m\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def ok(mid, pills, strength, tl, tr, wl, wr):\n",
    "            t = 0\n",
    "            h = 0\n",
    "            cnts = 0\n",
    "            i = wl\n",
    "            j = tl\n",
    "            while i <= wr:\n",
    "                while j <= tr and tasks[j] <=workers[i]:\n",
    "                    arr[t] = j\n",
    "                    t += 1\n",
    "                    j += 1\n",
    "                if t > h and workers[i] >= tasks[arr[h]]:\n",
    "                    h += 1\n",
    "                else:\n",
    "                    while j <= tr and tasks[j] <= workers[i] + strength:\n",
    "                        arr[t] = j\n",
    "                        t += 1\n",
    "                        j += 1\n",
    "                    if t > h:\n",
    "                        t -= 1\n",
    "                        cnts += 1\n",
    "                    else:\n",
    "                        return False\n",
    "                i += 1\n",
    "            return pills >= cnts\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        arr = [0 for _ in range(50001)]\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        r = min(len(tasks), len(workers))\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if ok(mid, pills, strength, 0, mid - 1, len(workers) - mid, len(workers) - 1):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "        n = min(len(tasks), len(workers))\n",
    "        l,r = 0, n\n",
    "        while l < r:\n",
    "            mid = (l+r+1)//2\n",
    "            i2 = 0\n",
    "            valid_tasks = deque()\n",
    "            fail = False\n",
    "            p = pills\n",
    "            for j in range(len(workers)-mid,len(workers)):\n",
    "                w = workers[j]\n",
    "                while i2 < mid and tasks[i2] <= w+strength:\n",
    "                    valid_tasks.append(tasks[i2]) \n",
    "                    i2+=1\n",
    "                if not valid_tasks:\n",
    "                    fail = True\n",
    "                    break\n",
    "                if valid_tasks[0] <= w:\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    if not p:\n",
    "                        fail = True\n",
    "                        break\n",
    "                    p-=1\n",
    "                    valid_tasks.pop()\n",
    "            if fail:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(\n",
    "        self, tasks: List[int], workers: List[int], pills: int, strength: int\n",
    "    ) -> int:\n",
    "        def check(x):\n",
    "            i = 0\n",
    "            q = deque()\n",
    "            p = pills\n",
    "            for j in range(m - x, m):\n",
    "                while i < x and tasks[i] <= workers[j] + strength:\n",
    "                    q.append(tasks[i])\n",
    "                    i += 1\n",
    "                if not q:\n",
    "                    return False\n",
    "                if q[0] <= workers[j]:\n",
    "                    q.popleft()\n",
    "                elif p == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        left, right = 0, min(n, m)\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        # Step 1: Sort the tasks and workers arrays\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        # Step 2: Initialize binary search bounds\n",
    "        start, end = 0, min(len(tasks), len(workers)) + 1\n",
    "\n",
    "        # Step 3: Start the binary search loop\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end) // 2\n",
    "\n",
    "            # Step 4: Check feasibility of assigning 'mid' tasks to 'mid' workers\n",
    "            task_index = 0  # Pointer for tasks\n",
    "            remaining_pills = pills  # Counter for remaining pills\n",
    "            is_possible = True  # Flag to check if the assignment is possible\n",
    "            valid_tasks = deque()  # Store tasks that can possibly be performed by each worker\n",
    "\n",
    "            for worker_index in range(len(workers) - mid, len(workers)):\n",
    "                worker_strength = workers[worker_index]\n",
    "\n",
    "                # Add all tasks that the worker can possibly perform to valid_tasks\n",
    "                while task_index < mid and tasks[task_index] <= worker_strength + strength:\n",
    "                    valid_tasks.append(tasks[task_index])\n",
    "                    task_index += 1\n",
    "\n",
    "                # If no task is available for the worker, assignment is not possible\n",
    "                if not valid_tasks:\n",
    "                    is_possible = False\n",
    "                    break\n",
    "\n",
    "                # If the worker can complete a task without a pill, do so\n",
    "                if valid_tasks[0] <= worker_strength:\n",
    "                    valid_tasks.popleft()\n",
    "                else:\n",
    "                    # If a pill is needed, check availability\n",
    "                    if not remaining_pills:\n",
    "                        is_possible = False\n",
    "                        break\n",
    "                    remaining_pills -= 1\n",
    "                    valid_tasks.pop()         \n",
    "\n",
    "            # Update binary search bounds based on feasibility\n",
    "            if is_possible:\n",
    "                start = mid\n",
    "            else:\n",
    "                end = mid\n",
    "\n",
    "        return start\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            ws = deque()\n",
    "            ptr = m - 1\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                while ptr >= m - mid and workers[ptr] + strength >= tasks[i]:\n",
    "                    ws.appendleft(workers[ptr])\n",
    "                    ptr -= 1\n",
    "                if not ws:\n",
    "                    return False\n",
    "                # 如果双端队列中最大的元素大于等于 tasks[i]\n",
    "                elif ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.popleft()\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = workers[m - mid:]\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = bisect_left(ws, tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxTaskAssign(self, tasks, workers, pills, strength):\n",
    "\t\ttasks.sort()\n",
    "\t\tworkers.sort()\n",
    "\t\treturn self.bs(tasks, workers, pills, strength, 0, min(len(tasks), len(workers)) + 1)\n",
    "\t\n",
    "\tdef bs(self, ts, ws, n, add, l, r):\n",
    "\t\tif l >= r:\n",
    "\t\t\treturn r - 1\n",
    "\t\tm = (l + r) >> 1\n",
    "\t\tif self.chk(ts, ws, n, add, m):\n",
    "\t\t\treturn self.bs(ts, ws, n, add, m + 1, r)\n",
    "\t\telse:\n",
    "\t\t\treturn self.bs(ts, ws, n, add, l, m)\n",
    "\t\n",
    "\tdef chk(self, ts, ws, n, add, m):\n",
    "\t\tl = len(ws)\n",
    "\t\twi = l - 1\n",
    "\t\tflag = [False] * l\n",
    "\t\tnxt = list(range(l + 1))\n",
    "\t\tfor ti in range(m - 1, -1, -1):\n",
    "\t\t\tif ws[wi] >= ts[ti]:\n",
    "\t\t\t\twi -= 1\n",
    "\t\t\t\twhile wi >= 0 and flag[wi]:\n",
    "\t\t\t\t\twi -= 1\n",
    "\t\t\telif n > 0:\n",
    "\t\t\t\tidx = bisect.bisect_left(ws, ts[ti] - add)\n",
    "\t\t\t\tif nxt[idx] > wi:\n",
    "\t\t\t\t\treturn False\n",
    "\t\t\t\tflag[nxt[idx]] = True\n",
    "\t\t\t\tnxt[idx] = self.update(nxt, nxt[idx] + 1)\n",
    "\t\t\t\tn -= 1\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn False\n",
    "\t\treturn True\n",
    "\t\n",
    "\tdef update(self, nxt, i):\n",
    "\t\tif nxt[i] != i:\n",
    "\t\t\tnxt[i] = self.update(nxt, nxt[i])\n",
    "\t\treturn nxt[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        \n",
    "        def checkK(k): # check k个 tasks是否可完成\n",
    "            stack = deque() # 可完成当前task的工人: 双端队列\n",
    "            p = pills\n",
    "            widx = 0\n",
    "            for t in tasks[:k][::-1]:  # t: 当前待审查任务\n",
    "                while widx < k and workers[widx] + strength >= t: # 把能完成当前t的\"新工人\"加入队列\n",
    "                    stack.append(workers[widx])\n",
    "                    widx += 1\n",
    "                if not stack:\n",
    "                    return False\n",
    "                if stack[0] >= t: # \"最大\"工人用 自然之力就可完成\n",
    "                    stack.popleft()\n",
    "                    continue\n",
    "                elif p <= 0: # 没药了\n",
    "                    return False\n",
    "                else: # \"最小\"工人 磕药\n",
    "                    p -= 1\n",
    "                    stack.pop()\n",
    "            return True\n",
    "        \n",
    "\n",
    "        tasks.sort()\n",
    "        workers.sort(reverse=True)\n",
    "        # 二分搜索最大可行 k\n",
    "        l, r = 0, min(len(tasks), len(workers)) + 1\n",
    "        while r-l > 1:\n",
    "            m = (l+r) // 2\n",
    "            if checkK(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        \n",
    "        return l\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        \n",
    "        def checkK(k):\n",
    "            stack = deque()\n",
    "            p = pills\n",
    "            widx = 0\n",
    "            for t in tasks[-k:]:\n",
    "                while widx < k and workers[widx] + strength >= t:\n",
    "                    stack.append(workers[widx])\n",
    "                    widx += 1\n",
    "                if not stack:\n",
    "                    return False\n",
    "                if stack[0] >= t:\n",
    "                    stack.popleft()\n",
    "                    continue\n",
    "                elif p <= 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    p -= 1\n",
    "                    stack.pop()\n",
    "            return True\n",
    "        \n",
    "        tasks.sort(reverse=True)\n",
    "        workers.sort(reverse=True)\n",
    "\n",
    "        l, r = 0, min(len(tasks), len(workers)) + 1\n",
    "\n",
    "        while r-l > 1:\n",
    "            m = (l+r) // 2\n",
    "            if checkK(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        \n",
    "        return l\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        m, n = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        # 假设 K 个任务可以完成\n",
    "        def check(k) -> bool:\n",
    "            p = pills\n",
    "            ws = deque()\n",
    "            ptr = n -1\n",
    "            for i in range(k - 1, -1, -1):\n",
    "                while ptr >= n - k and workers[ptr] + strength >= tasks[i]:\n",
    "                    ws.appendleft(workers[ptr])\n",
    "                    ptr -= 1\n",
    "                if not ws:\n",
    "                    return False\n",
    "                elif ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        ws.popleft()\n",
    "                        p -= 1\n",
    "            return True\n",
    "\n",
    "\n",
    "        l, r, ans = 1, min(m, n), 0\n",
    "        while l <= r:\n",
    "            mid = (l + r)//2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        m, n = len(workers), len(tasks)\n",
    "        tasks.sort()\n",
    "        workers.sort(reverse=True)\n",
    "\n",
    "\n",
    "        def check(mid):\n",
    "            s = SortedList()\n",
    "            for i in range(mid):\n",
    "                s.add(workers[i])\n",
    "            p = pills\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                t = tasks[i]\n",
    "                if s[-1] >= t:\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    if not p or s[-1] + strength < t:\n",
    "                        return True\n",
    "                    idx = s.bisect_left(t - strength)\n",
    "                    s.pop(idx)\n",
    "                    p -= 1\n",
    "            return False\n",
    "\n",
    "        t = min(m, n)\n",
    "        return bisect_left(range(t + 1), 1, key=check) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "        m, n = len(workers), len(tasks)\n",
    "\n",
    "        def canFinish(k):\n",
    "            if k > m:\n",
    "                return False\n",
    "            w = SortedList(workers[-k:])\n",
    "            t = tasks[:k][::-1]\n",
    "            p = pills\n",
    "\n",
    "            for x in t:\n",
    "                if w[-1] >= x:\n",
    "                    w.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    idx = bisect.bisect_left(w, x - strength)\n",
    "                    if idx >= len(w):\n",
    "                        return False\n",
    "                    w.pop(idx)\n",
    "                    p -= 1\n",
    "\n",
    "            return True\n",
    "\n",
    "\n",
    "        \n",
    "        low, high = 0, n\n",
    "        while low <= high:\n",
    "            mid = low + (high-low) // 2\n",
    "            if canFinish(mid):\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        \n",
    "        return low - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort(reverse=True)\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            worker = workers[0:k]\n",
    "            worker.reverse()\n",
    "            for i in range(k):\n",
    "                while j < k and worker[i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if worker[i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__()) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            ws = deque()\n",
    "            ptr = m - 1\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                while ptr >= m - mid and workers[ptr] + strength >= tasks[i]:\n",
    "                    ws.appendleft(workers[ptr])\n",
    "                    ptr -= 1\n",
    "                if not ws:\n",
    "                    return False\n",
    "                # 如果双端队列中最大的元素大于等于 tasks[i]\n",
    "                elif ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.popleft()\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort(reverse=True)\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            worker = workers[0:k]\n",
    "            worker.reverse()\n",
    "            for i in range(k):\n",
    "                while j < k and worker[i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if worker[i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__()) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        tasks.sort()\n",
    "        workers.sort(reverse = True)\n",
    "        def check(val):\n",
    "            cnt = pills\n",
    "            man = SortedList(workers[:val])\n",
    "            for i in range(val-1,-1,-1):\n",
    "                if man and man[-1]>=tasks[i]:\n",
    "                    man.pop(-1)\n",
    "                else:\n",
    "                    if cnt == 0:\n",
    "                        return False\n",
    "                    idx = bisect_left(man,tasks[i]-strength)\n",
    "                    if idx<len(man):\n",
    "                        man.pop(idx)\n",
    "                        cnt -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "            return True\n",
    "        l,r = 1,len(tasks)\n",
    "        while l<=r:\n",
    "            mid = (l+r)>>1\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid -1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            \n",
    "            start = workers.__len__() - k\n",
    "            for i in range(k):\n",
    "                while j < k and workers[start+i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if workers[start+i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__()) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort(reverse=True)\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            worker = workers[0:k]\n",
    "            worker.reverse()\n",
    "            for i in range(k):\n",
    "                while j < k and worker[i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if worker[i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__()) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        from collections import deque\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort(reverse = True)\n",
    "\n",
    "        def check(mid):\n",
    "            p = pills\n",
    "            ws = deque()\n",
    "            pt = 0\n",
    "            for i in range(mid-1, -1, -1):\n",
    "                while pt < mid and workers[pt] + strength >= tasks[i]:\n",
    "                    ws.appendleft(workers[pt])\n",
    "                    pt += 1\n",
    "                if not ws: return False\n",
    "                if ws[-1] >= tasks[i]: ws.pop()\n",
    "                else:\n",
    "                    if p == 0: return False\n",
    "                    p -= 1\n",
    "                    ws.popleft()\n",
    "            return True\n",
    "\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def complete(k: int, pills: int) -> bool:\n",
    "            \"\"\"whether the first k workers with largest strength can complete the first k tasks which need smallest strength O(k^2)\n",
    "            \"\"\"\n",
    "            # O(klogk) the first k workers with largest strength\n",
    "            sortedworkers = deque([])\n",
    "            j = 0\n",
    "            # O(klogk) iterates over the first k tasks which need smallest strength by descending order of strength\n",
    "            for i in range(n-k, n):\n",
    "                while j < mid and workers[j] + strength >= tasks[i]:\n",
    "                    sortedworkers.append(workers[j])\n",
    "                    j += 1\n",
    "                if not sortedworkers:\n",
    "                    return False \n",
    "                # 1. the worker with largest strength can complete the task\n",
    "                if sortedworkers[0] >= tasks[i]:\n",
    "                    sortedworkers.popleft()  # O(1)\n",
    "                # no worker can complete the task without a pill\n",
    "                else:\n",
    "                    # no pill left, can't complete the task\n",
    "                    if pills == 0:\n",
    "                        return False\n",
    "                    # the worker with smallest strength (>= task[i]-strength) take a pill to complete the task\n",
    "                    else:\n",
    "                        pills -= 1\n",
    "                        sortedworkers.pop()  # O(1)\n",
    "            return True\n",
    "\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort(reverse=True)    # O(nlogn) sort the task by strength descendingly\n",
    "        workers.sort(reverse=True)  # O(mlogm) sort the worker by strength descendingly\n",
    "\n",
    "        left, right = 1, min(m, n)\n",
    "        ans = 0\n",
    "\n",
    "        # O(klog^2k) k=min(m, n)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if complete(mid, pills):    # O(klogk) \n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            \n",
    "            start = workers.__len__() - k\n",
    "            for i in range(k):\n",
    "                while j < k and workers[start+i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if workers[start+i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__())\n",
    "        while lo <= hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid - 1\n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def needYNum(rs:list,ws:list,R:int,YL:int):\n",
    "            if len(ws)<R:return +inf\n",
    "            help=deque()\n",
    "            ri,Ynums=0,0\n",
    "            for w in ws[-R:]:\n",
    "                while ri<R and rs[ri] <= w:\n",
    "                    help.append(rs[ri])\n",
    "                    ri+=1\n",
    "                if help and help[0]<=w:\n",
    "                    help.popleft()\n",
    "                else:\n",
    "                    while ri<R and rs[ri] <= w+YL:\n",
    "                        help.append(rs[ri])\n",
    "                        ri+=1   \n",
    "                    if help:\n",
    "                        help.pop()\n",
    "                        Ynums+=1\n",
    "                        if Ynums>pills:\n",
    "                            break\n",
    "                    elif ri<R: return +inf\n",
    "                    else:break\n",
    "            return Ynums\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        l,r=0,min(len(tasks),len(workers))\n",
    "        mindex,ans=0,0\n",
    "        while l<=r:\n",
    "            mindex=(l+r)//2\n",
    "            maxY=needYNum(tasks,workers,mindex,strength)\n",
    "            if maxY<=pills:\n",
    "                l=mindex+1\n",
    "                ans=mindex\n",
    "            else:\n",
    "                r=mindex-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        \n",
    "        \n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        #aa = [1, 2, 4, 5, 7]\n",
    "        #bisect.bisect_left(aa, )\n",
    "        m = len(tasks)\n",
    "        n = len(workers)\n",
    "        \n",
    "        #p\n",
    "        \n",
    "        def can_finish(x):\n",
    "            \n",
    "            need = 0\n",
    "            t = SortedList(tasks[:x])\n",
    "            for i in range(n-x, n):\n",
    "                if workers[i] >= t[0]:\n",
    "                    #if x == 3:\n",
    "                    #    print(workers[i], tasks[0])\n",
    "                    t.pop(0)\n",
    "                    continue\n",
    "\n",
    "                if workers[i] + strength < t[0]:\n",
    "                    return False\n",
    "\n",
    "                index = t.bisect_right(workers[i] + strength)\n",
    "                \n",
    "                t.pop(index - 1)\n",
    "                need += 1\n",
    "                \n",
    "            return need <= pills                \n",
    "\n",
    "            #print()\n",
    "\n",
    "        l = 0\n",
    "        r = min(n + 1, m + 1)\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if can_finish(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        #print(can_finish(130))\n",
    "                \n",
    "        return l\n",
    "\n",
    "\n",
    "                        \n",
    "                        \n",
    "\n",
    "                            \n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            \n",
    "            start = workers.__len__() - k\n",
    "            for i in range(k):\n",
    "                while j < k and workers[start+i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if workers[start+i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__()) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def check(k):\n",
    "            cur = pills\n",
    "            lst = SortedList(workers[-k:])\n",
    "            for i in range(k-1, -1, -1):\n",
    "                if lst[-1] >= tasks[i]:\n",
    "                    lst.pop()\n",
    "                else:\n",
    "                    j = bisect_left(lst,tasks[i] - strength)\n",
    "                    if not cur or j == len(lst):\n",
    "                        return False\n",
    "                    cur -= 1\n",
    "                    lst.pop(j)\n",
    "            return True\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        n, m = len(tasks), len(workers)\n",
    "        low = 0\n",
    "        high = min(m, n)\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "    \n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(mid):\n",
    "            p = pills\n",
    "            ws = workers[len(workers)-mid:]\n",
    "            #tsk = tasks[:mid]\n",
    "            for i in range(mid-1,-1,-1):\n",
    "                if ws[-1]>=tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = bisect.bisect_left(ws, tasks[i]-strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "\n",
    "        l = 1\n",
    "        r = min(len(workers),len(tasks))\n",
    "        res = 0\n",
    "\n",
    "        while l<= r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                res = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            \n",
    "            start = workers.__len__() - k\n",
    "            for i in range(k):\n",
    "                while j < k and workers[start+i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if workers[start+i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__()) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        # left, right, ans = 1, min(m, n), 0\n",
    "        left, right = -1, min(m, n)+1\n",
    "        while left +1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort(reverse=True)\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "           \n",
    "            for i in range(k):\n",
    "                while j < k and workers[k-1-i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if workers[k-1-i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__()) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks, workers, pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int):\n",
    "            p = pills\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "\n",
    "            for i in range(mid-1, -1, -1):\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "\n",
    "        left, right = 1, min(m, n)\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        last_result = 0\n",
    "        def check(mid: int) -> bool:\n",
    "            nonlocal  last_result\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = workers[m - mid:]\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return 1\n",
    "                    rep = bisect.bisect_left(ws,tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return 1\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            last_result = max(last_result, mid)\n",
    "            return -1\n",
    "        \n",
    "        bisect.bisect_left(range(min(m,n)+1), 0, key=check)\n",
    "        return last_result\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n,m=len(tasks),len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid:int)->bool:\n",
    "            p=pills\n",
    "            #工人的有序集合\n",
    "            #ws=workers[m-mid:].sort()\n",
    "            ws=SortedList(workers[m-mid:])\n",
    "            for i in range(mid-1,-1,-1):\n",
    "                if ws[-1]>=tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p==0:\n",
    "                        return False\n",
    "                    rep=ws.bisect_left(tasks[i]-strength)\n",
    "                    if rep==len(ws):\n",
    "                        return False\n",
    "                    p-=1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "        left,right,ans=1,min(m,n),0\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                ans=mid\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        \n",
    "        def check(x):\n",
    "            tmp = pills\n",
    "            ws = SortedList(workers[-x:])\n",
    "            for i in range(x-1,-1,-1):\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    #idx = bisect.bisect_left(ws,tasks[i])\n",
    "                    #ws.pop(idx)\n",
    "                    ws.pop()\n",
    "                elif tmp == 0 or ws[-1] + strength < tasks[i]:\n",
    "                        return False\n",
    "                else:\n",
    "                    idx = bisect.bisect_left(ws,tasks[i] - strength)\n",
    "                    tmp -= 1\n",
    "                    ws.pop(idx)\n",
    "            return True\n",
    "        '''\n",
    "        def check(x):\n",
    "            tmp = pills\n",
    "            ws = workers[-x:]\n",
    "            #print(ws)\n",
    "            q = deque([])\n",
    "            j = 0\n",
    "            for i in range(x):\n",
    "                while j < x and tasks[j] <= ws[i] + strength:\n",
    "                    q.append(tasks[j])\n",
    "                    j += 1\n",
    "                #print(q,ws[i])\n",
    "                if not q:\n",
    "                    return False\n",
    "                if q[0] <= ws[i]:\n",
    "                    q.popleft()\n",
    "                elif tmp > 0:\n",
    "                    q.pop()\n",
    "                    tmp -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        '''\n",
    "\n",
    "        left,right = 0,min(len(tasks),len(workers))\n",
    "        #ans = right\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            #print(mid)\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            \n",
    "            start = workers.__len__() - k\n",
    "            for i in range(k):\n",
    "                while j < k and workers[start+i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                   \n",
    "                    return False\n",
    "\n",
    "                if workers[start+i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__())\n",
    "        while lo <= hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid - 1\n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort(reverse=True)\n",
    "        tasks.sort()\n",
    "\n",
    "        def check(k):\n",
    "            p = pills\n",
    "            q = deque()\n",
    "            j = 0\n",
    "            worker = workers[0:k]\n",
    "            # worker.reverse()\n",
    "            for i in range(k):\n",
    "                while j < k and worker[k-1-i] + strength >= tasks[j]:\n",
    "                    q.append(j)\n",
    "                    j += 1\n",
    "                \n",
    "                if not q:\n",
    "                    if j < k:\n",
    "                        return False\n",
    "\n",
    "                if worker[k-1-i] >= tasks[q[0]]:\n",
    "                    q.popleft()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    q.pop()\n",
    "            return True\n",
    "        \n",
    "        lo = 0 \n",
    "        hi = min(workers.__len__(), tasks.__len__()) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        last_result = 0\n",
    "        def check(mid: int) -> bool:\n",
    "            nonlocal  last_result\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return 1\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return 1\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            last_result = max(last_result, mid)\n",
    "            return -1\n",
    "        \n",
    "        bisect.bisect_left(range(min(m,n)+1), 0, key=check)\n",
    "        return last_result\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from bisect import bisect_left\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n,m = len(tasks),len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(k:int)->bool:\n",
    "            # worker_list = SortedList(workers[m-k:])\n",
    "            worker_list = workers[m-k:]\n",
    "            use = 0\n",
    "            for i in range(k-1,-1,-1):\n",
    "                if worker_list[-1]>=tasks[i]:\n",
    "                    worker_list.pop(-1)\n",
    "                else:\n",
    "                    if use == pills:\n",
    "                        return False\n",
    "                    else:\n",
    "                        use += 1\n",
    "                        # idx = worker_list.bisect_left(tasks[i]-strength)\n",
    "                        idx = bisect_left(worker_list, tasks[i]-strength)\n",
    "                        if idx == len(worker_list):\n",
    "                            return False\n",
    "                        worker_list.pop(idx)\n",
    "                pass\n",
    "            return True\n",
    "\n",
    "        l,r = 0,min(n,m)\n",
    "        res = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if(check(mid)):\n",
    "                l = mid+1\n",
    "                res = mid\n",
    "            else: r=mid-1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            # 工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    # 在有序集合中找到第一个大于等于 tasks[i] - strength 的位置\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# 示例用法\n",
    "ts = [10, 15, 30]\n",
    "ws = [0, 10, 10, 10, 10]\n",
    "pills = 3\n",
    "strength = 10\n",
    "\n",
    "solution = Solution()\n",
    "result = solution.maxTaskAssign(ts, ws, pills, strength)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def check(mid: int, pills: int) -> bool:\n",
    "            #  工人的有序集合\n",
    "            sortedworkers = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(n-mid, n):\n",
    "                # the worker with largest strength complete the task\n",
    "                if sortedworkers[-1] >= tasks[i]:\n",
    "                    sortedworkers.pop()\n",
    "                # no worker can complete the task without a pill\n",
    "                else:\n",
    "                    # no pill left, can't complete the task\n",
    "                    if pills == 0:\n",
    "                        return False\n",
    "                    # the worker with smallest strength (>= task[i]-strength) take a pill to complete the task\n",
    "                    else:\n",
    "                        idx = sortedworkers.bisect_left(tasks[i] - strength)\n",
    "                        if idx == len(sortedworkers):\n",
    "                            return False\n",
    "                        else:\n",
    "                            pills -= 1\n",
    "                            sortedworkers.pop(idx)\n",
    "            return True\n",
    "\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort(reverse=True)\n",
    "        workers.sort()\n",
    "\n",
    "        left, right = 1, min(m, n)\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid, pills):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def check(ts, ws):\n",
    "            p, s = pills, strength\n",
    "            for i in range(len(ws)):\n",
    "                if ws[i] >= ts[0]:\n",
    "                    ts.pop(0)\n",
    "                else:\n",
    "                    # <idx ==> <=target\n",
    "                    idx = ts.bisect_right(ws[i]+s)\n",
    "                    if idx == 0 or p==0:\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ts.pop(idx-1)\n",
    "            return True\n",
    "\n",
    "        m, n = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        lo, hi = -1, min(m, n)+1\n",
    "        while lo+1<hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(SortedList(tasks[:mid]), workers[n-mid:n]):\n",
    "                lo = mid\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def complete(k: int, pills: int) -> bool:\n",
    "            \"\"\"whether the first k workers with largest strength can complete the first k tasks which need smallest strength O(k^2)\n",
    "            \"\"\"\n",
    "            # O(klogk) the first k workers with largest strength\n",
    "            sortedworkers = SortedList(workers[m-k:])\n",
    "            length = k \n",
    "            # O(k^2) iterates over the first k tasks which need smallest strength by descending order of strength\n",
    "            for i in range(n-k, n):\n",
    "                # 1. the worker with largest strength can complete the task\n",
    "                if sortedworkers[-1] >= tasks[i]:\n",
    "                    sortedworkers.pop()\n",
    "                    length -= 1\n",
    "                # no worker can complete the task without a pill\n",
    "                else:\n",
    "                    # no pill left, can't complete the task\n",
    "                    if pills == 0:\n",
    "                        return False\n",
    "                    # the worker with smallest strength (>= task[i]-strength) take a pill to complete the task\n",
    "                    else:\n",
    "                        idx = sortedworkers.bisect_left(tasks[i] - strength)    # O(logk)\n",
    "                        if idx == length:   # O(k)\n",
    "                            return False\n",
    "                        else:\n",
    "                            pills -= 1\n",
    "                            sortedworkers.pop(idx)  # O(logk)\n",
    "                            length -= 1\n",
    "            return True\n",
    "\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort(reverse=True)    # O(nlogn) sort the task by strength descendingly\n",
    "        workers.sort()  # O(mlogm) sort the worker by strength ascendingly\n",
    "\n",
    "        left, right = 1, min(m, n)\n",
    "        ans = 0\n",
    "\n",
    "        # O(log min(m, n))\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if complete(mid, pills):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            # 工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    # 在有序集合中找到第一个大于等于 tasks[i] - strength 的位置\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# 示例用法\n",
    "ts = [10, 15, 30]\n",
    "ws = [0, 10, 10, 10, 10]\n",
    "pills = 3\n",
    "strength = 10\n",
    "\n",
    "solution = Solution()\n",
    "result = solution.maxTaskAssign(ts, ws, pills, strength)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        \n",
    "        def check(workers, tasks):\n",
    "            c = 0#药丸数量\n",
    "            while tasks:#降序弹出\n",
    "                n = tasks.pop()\n",
    "                if workers[-1] + strength < n:#如果加上药丸都无法完成\n",
    "                    return False\n",
    "                elif workers[-1] < n:#需要吃药丸\n",
    "                    idx = bisect.bisect_left(workers, n - strength)\n",
    "                    #二分找到可以吃药丸完成任务中最小的工人\n",
    "\n",
    "                    workers.pop(idx)#弹出该工人\n",
    "                    c += 1#药丸数量+1\n",
    "\n",
    "                    if c > pills:#如果超出药丸总数则无法完成\n",
    "                        return False\n",
    "\n",
    "                else:#不需要吃药丸\n",
    "                    workers.pop()#弹出最强的\n",
    "            return True\n",
    "\n",
    "        tasks.sort()#排序\n",
    "        workers.sort()\n",
    "        l = 0#左边界\n",
    "        r = min(len(tasks), len(workers))#右边界\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            if check(workers[-mid:], tasks[:mid]):#可以完成，更新左边界\n",
    "                l = mid\n",
    "            else:#无法完成，更新右边界\n",
    "                r = mid - 1\n",
    "        return l\n",
    "#二分查找最多完成任务。 每次二分查找到的任务数量，按照降序取出对应数量工人，按照升序取出对应数量任务。 降序遍历任务，当任务比当前最强的工人加上药丸力量还大时，说明无法完成对应数量任务。 当任务比当前最强的工人力量大时，二分找到吃下药丸后能完成任务的最小工人完成任务，并将药丸数量+1。 否则将最强工人弹出，因为任务和工人都是有序的，如果存在更小的工人可以完成此任务那么一定能完成剩余任务，所以这里不需要再二分。 结束后如果药丸数量不大于pills时则说明可以完成，更新左边界，否则无法完成更新右边界。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        workers.sort()\n",
    "        tasks.sort()\n",
    "        wn = len(workers)\n",
    "        def isValid(k):\n",
    "            wks = SortedList(workers[wn-k:])\n",
    "            pill = pills\n",
    "            # print(wks)\n",
    "            for taskIndex in range(k-1, -1, -1):\n",
    "                w = tasks[taskIndex]\n",
    "                # print(w)\n",
    "                if not wks: return False\n",
    "                if w <= wks[-1]: \n",
    "                    wks.pop()\n",
    "                else:\n",
    "                    if pill == 0: return False\n",
    "                    worker = wks.bisect_left(w-strength)\n",
    "                    if worker == len(wks):\n",
    "                        return False\n",
    "                    wks.pop(worker)\n",
    "                    pill-=1\n",
    "            return True\n",
    "        \n",
    "        leftK = 0\n",
    "        rightK = min(len(tasks), len(workers))\n",
    "        while leftK + 1 < rightK:\n",
    "            midK = (leftK+rightK)//2\n",
    "            if isValid(midK):\n",
    "                leftK = midK\n",
    "            else:\n",
    "                rightK = midK\n",
    "        if isValid(rightK): return rightK\n",
    "        if isValid(leftK): return leftK\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def check(x):\n",
    "            w = SortedList(workers[m - mid:])\n",
    "            cnt = pills\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                if w[-1] >= tasks[i]:\n",
    "                    w.pop()\n",
    "                else:\n",
    "                    if cnt == 0:\n",
    "                        return False\n",
    "                    idx = w.bisect_left(tasks[i] - strength)\n",
    "                    if idx == len(w):\n",
    "                        return False \n",
    "                    cnt -= 1\n",
    "                    w.pop(idx)\n",
    "            return True \n",
    "\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        left, right, ret = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            if check(mid):\n",
    "                ret = mid \n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        \n",
    "        def check(mid: int) -> bool:\n",
    "            p = pills\n",
    "            #  工人的有序集合\n",
    "            ws = SortedList(workers[m - mid:])\n",
    "            # 从大到小枚举每一个任务\n",
    "            for i in range(mid - 1, -1, -1):\n",
    "                # 如果有序集合中最大的元素大于等于 tasks[i]\n",
    "                if ws[-1] >= tasks[i]:\n",
    "                    ws.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    rep = ws.bisect_left(tasks[i] - strength)\n",
    "                    if rep == len(ws):\n",
    "                        return False\n",
    "                    p -= 1\n",
    "                    ws.pop(rep)\n",
    "            return True\n",
    "\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        n, m = len(tasks), len(workers)\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        l = 1\n",
    "        r = min(n,m)\n",
    "        def check(mid,p):\n",
    "            tasks_select = tasks[:mid]\n",
    "            workers_select = workers[-mid:]\n",
    "            for i in range(mid-1,-1,-1):\n",
    "                if tasks_select[i] <= workers_select[-1]:\n",
    "                    workers_select.pop()\n",
    "                else:\n",
    "                    if p == 0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        # for j in range(len(workers_select)):\n",
    "                        #     if workers_select[j]+strength >= tasks_select[i]:\n",
    "                        #         p = p-1\n",
    "                        #         workers_select.pop(j)\n",
    "                        #         break\n",
    "                        #     else:\n",
    "                        #         if j == len(workers_select)-1:\n",
    "                        #             return False\n",
    "                        obj = bisect_left(workers_select,tasks_select[i]-strength) ##二分查找函数：https://blog.csdn.net/YMWM_/article/details/122378152\n",
    "                        if obj == len(workers_select): ## !!!\n",
    "                            return False\n",
    "                        p = p-1\n",
    "                        workers_select.pop(obj)\n",
    "                        \n",
    "            return True   \n",
    "        ans = 0      \n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if check(m, pills):\n",
    "                ans = m\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        nt = len(tasks)\n",
    "        nw = len(workers)\n",
    "        tasks.sort(key=lambda x:-x)\n",
    "        workers.sort(key=lambda x:-x)\n",
    "\n",
    "        def need_pills(tasks, workers):\n",
    "            num_pills = pills\n",
    "            while len(workers)>0:\n",
    "                w = workers.pop()\n",
    "                if w>=tasks[-1]:\n",
    "                    tasks.pop()\n",
    "                else:\n",
    "                    if num_pills>0 and w+strength>=tasks[-1]:\n",
    "                        for i in range(len(tasks)):\n",
    "                            if w+strength>=tasks[i]:\n",
    "                                break\n",
    "                        tasks.pop(i)\n",
    "                        num_pills -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "            return True\n",
    "            \n",
    "            \n",
    "        i = 0\n",
    "        j = min(nt, nw)\n",
    "        right = j+1\n",
    "        while i<=j:\n",
    "            mid = (i+j)//2\n",
    "            a = need_pills(tasks[-mid:], workers[:mid])\n",
    "            if not a:\n",
    "                right = mid\n",
    "                j = mid-1\n",
    "            else:\n",
    "                i = mid+1\n",
    "        \n",
    "        return right-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:\n",
    "        def check(k):\n",
    "            cur = pills\n",
    "            lst = SortedList(workers[-k:])\n",
    "            for i in range(k-1, -1, -1):\n",
    "                if lst[-1] >= tasks[i]:\n",
    "                    lst.pop()\n",
    "                else:\n",
    "                    j = lst.bisect_left(tasks[i] - strength)\n",
    "                    if not cur or j == len(lst):\n",
    "                        return False\n",
    "                    cur -= 1\n",
    "                    lst.pop(j)\n",
    "            return True\n",
    "        tasks.sort()\n",
    "        workers.sort()\n",
    "        n, m = len(tasks), len(workers)\n",
    "        low = 0\n",
    "        high = min(m, n)\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
